#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution
{
public:
    vector<vector<string>> ret;
    vector<string> path;
    int n;
    // 我们一行一行来方Q，所以一行里面一定有值
    // bool checkcol[10]; //该列是不是有皇后
    // bool checkdig1[2*10];//斜对角线是不是有皇后
    // bool checkdig2[2*10];//反斜对角是不是有皇后
    vector<bool> checkcol;  // 该列是不是有皇后
    vector<bool> checkdig1; // 斜对角线是不是有皇后
    vector<bool> checkdig2; // 反斜对角是不是有皇后
    void dfs(int row)       // row是行
    {
        if (row == n)
        {
            ret.push_back(path);
            return;
        }
        for (int col = 0; col < n; ++col)
        {
            // 主对角线：y-x = b，可能为负数，所以同时加上n --- >>>  y-x+n = b+n;
            // 副对角线:y+x = b
            // 剪枝，判断该皇后所在的列，斜对角，反斜对角是否存在皇后了
            if (checkcol[col] == false && checkdig1[row - col + n] == false && checkdig2[row + col] == false)
            {
                path[row][col] = 'Q';
                // 该位置插入皇后，那么该位置对应的列，斜对角，反斜对角就不能再有皇后了！
                checkcol[col] = checkdig1[row - col + n] = checkdig2[row + col] = true;
                dfs(row + 1); // 注意是row行+1，不是col
                // 回来，恢复现场
                checkcol[col] = checkdig1[row - col + n] = checkdig2[row + col] = false;
                path[row][col] = '.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int _n)
    {
        n = _n;
        checkcol.resize(n);      // 一列判断n个空间就够了
        checkdig1.resize(2 * n); // 斜对角的判断，需要row - col + n = b + n 其中row和col就是n行n列，所以最大需要2n个空间
        checkdig2.resize(2 * n); // 反斜对角的判断同理，需要row + col= b 其中row和col就是n行n列，所以最大需要2n个空间
        path.resize(n, string(n, '.'));
        dfs(0);
        return ret;
    }
};
class Solution
{
public:
    // bool row[n][n+1] : row的第n行中,是否出现了第n+1个数，出现了true，没有出现false
    // bool col[n][n+1] : col的第n列中,是否出现了第n+1个数，出现了true，没有出现false
    // 判断一个3*3的小方格中有没有出现重复的数
    // 我们开一个三维数组 grid[3][3][n+1] : 将行和列3个3个一组划分，那么不管是哪一个数，横纵左边除以3就在grid里面，在看是否出现了n+1
    bool row[9][10];
    bool col[9][10];
    bool grid[3][3][10];
    bool isValidSudoku(vector<vector<char>> &board)
    {
        for (int i = 0; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                if (board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    // 下面3种情况有一种成立，表示我num这个数出现过了，那么就不是有效数独
                    if (row[i][num] == true || col[j][num] == true || grid[i / 3][j / 3][num] == true)
                    {
                        return false;
                    }
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }
            }
        }
        return true;
    }
};

class Solution {
public:
    // bool row[n][n+1] : row的第n行中,是否出现了第n+1个数，出现了true，没有出现false
    // bool col[n][n+1] : col的第n列中,是否出现了第n+1个数，出现了true，没有出现false
    // 判断一个3*3的小方格中有没有出现重复的数
    // 我们开一个三维数组 grid[3][3][n+1] : 将行和列3个3个一组划分，那么不管是哪一个数，横纵左边除以3就在grid里面，在看是否出现了n+1
    bool row[9][10];
    bool col[9][10];
    bool grid[3][3][10];
    // 要注意，虽然题目说必定有结果，但是我们要注意 ：【我第一个位置可以填2,3,4.但是只有填3后面才能推完整个过程，2,4不可以！】
    // 所以我们的dfs一定要有一个返回值
    bool dfs(vector<vector<char>>& board)
    {
        for(int i=0;i<9;++i)
        {
            for(int j=0;j<9;++j)
            {
                if(board[i][j] == '.')
                {
                    // 开始填数，依次从1到9进行测试填写
                    for(int num=1;num<=9;++num)
                    {
                        if(row[i][num]==false && col[j][num]==false && grid[i/3][j/3][num]==false)
                        {
                            board[i][j] = num + '0';
                            // 这个位置用过了，要标志
                            row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;
                            if(dfs(board) == true) // 判断一下我这个位置填的这个数是不是正确的，如果是直接返回true就行，调用函数没有返回值
                            {
                                return true;
                            }
                            // 如果不是！！！恢复现场
                            // 解除标志
                            row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;
                            board[i][j] = '.';
                        }
                    }
                    // 该位置1到9都没有返回true，那么就说明这个九宫格不能正确填写
                    return false;
                }
            }
        }
        // 这里就是把九宫格都填写完毕了，得到了正确结果
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) 
    {
        for(int i=0;i<9;++i)
        {
            for(int j=0;j<9;++j)
            {
                if(board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    // 先将九宫格里面已经有的数给标记好
                    row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;
                }
            }
        }
        dfs(board);
    }
};